package com.example.linklist;

/**
 * 链表
 * Created by 3020mt on 2016/3/17.
 */
public class LinkList<T>{
    public LinkNode<T> linkList; //内部链表

    /**
     * 根据目标数组生成链表
     * @param targets
     */
    public void createLinkedList(T [] targets){
        if(targets.length==0){
            return ;
        }
        LinkNode headNode = new LinkNode(targets[0]);
        this.linkList = headNode;
        LinkNode nextNode = null;
        if(targets.length==1){
        }
        else {
            nextNode = headNode;
        }
        for(int i=1;i<targets.length;i++){
            LinkNode linkNode = new LinkNode(targets[i]);
            nextNode.setNextNode(linkNode);
            nextNode = linkNode;
        }
        return ;
    }

    /**
     * 在某一位置增加节点
     * @param target
     * @param position
     */
    public void addNode(T target,int position){
        LinkNode targetNode = new LinkNode(target);
        if(isEmpty()){
            linkList = targetNode;
        }
        if(position==0){
            targetNode.setNextNode(linkList);
            linkList = targetNode;
        }
        else{
            LinkNode nextNode = linkList;
            for(int i = 0;i<position;i++){
                if(nextNode.getNextNode()!=null){
                    nextNode = nextNode.getNextNode();
                }
                else {
                    break;
                }
            }
            if(nextNode.getNextNode()!=null){
                LinkNode behindNode = nextNode.getNextNode();
                nextNode.setNextNode(targetNode);
                targetNode.setNextNode(behindNode);
            }
            else {
                nextNode.setNextNode(targetNode);
            }
        }
    }
    /**
     * 移除并返回某一个位置的元素
     * @param positon
     */
    public LinkNode removeNode(int positon){
        if(isEmpty()){
            return null;
        }
        if(positon==0){
            LinkNode headNode = linkList;
            LinkNode nextNode = linkList.getNextNode();
            if(nextNode!=null){
                linkList = nextNode;
            }
            headNode.setNextNode(null);
            return headNode;

        }
        LinkNode nextNode = linkList;
        for(int i = 0;i<positon;i++){
            if((nextNode = linkList.getNextNode())==null){
                return null;
            }
        }
        LinkNode removeNode = nextNode.getNextNode();
        nextNode.setNextNode(removeNode.getNextNode());
        removeNode.setNextNode(null);
        return  removeNode;
    }
    public void add(T target){
        LinkNode nextNode = linkList;
        while(nextNode.getNextNode()!=null){
            nextNode = nextNode.getNextNode();
        }
        nextNode.getNextNode().setNextNode(new LinkNode(target));
    }

    /**
     * 是否存在目标元素
     * @param target
     * @return
     */
    public boolean isContain(T target){
        LinkNode nextNode = linkList;
        if(nextNode.getTarget()==target){
            return true;
        }
        do{
            if(nextNode.getNextNode()==target){
                return true;
            }
        }while ((nextNode = nextNode.getNextNode())!=null);
        return false;
    }

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty(){
        if(linkList==null ){
            return true;
        }
        else {
            return false;
        }
    }
    public class LinkNode<T>{
        private T target;
        private LinkNode nextNode;
        LinkNode(T target){
            this.target = target;
        }
        public void setNextNode(LinkNode nextNode){
            this.nextNode = nextNode;
        }
        public LinkNode getNextNode(){
            return nextNode;
        }
        public T getTarget(){
            return  target;
        }
    }
}
